We exhibit a natural function F_n on n variables, computable by a linear sized decision list of "Equalities", but whose sign rank is exp(Omega(n^{1/4})). The simplicity of F_n yields the following two consequences.

1) F_n can be computed by linear sized depth-2 threshold formulas when the weights of the threshold gates are unrestricted (THR o THR), but any THR o MAJ circuit computing it requires size exp(Omega(n^{1/4})). This provides the first exponential separation between the boolean circuit complexity classes THR o MAJ and THR o THR, answering a question of Amano and Maruoka [MFCS'05] and Hansen and Podolskii [CCC'10].

In contrast, Goldmann, Hastad and Razborov [Computational Complexity'92] had shown more than 25 years ago that functions efficiently computable by MAJ o THR circuits can also be efficiently computed by MAJ o MAJ circuits. Thus, while weights at the bottom layer do not matter when the top is light, we discover that they do when the top is heavy.

2) The function F_n lies in the communication complexity class P^MA under the natural partition of the inputs. Since F_n has large sign rank, this implies P^MA is not a subset of UPP, strongly resolving a conjecture of Goos, Pitassi and Watson [ICALP'16].

In order to prove our main result, we view F_n as an XOR function, and develop a technique to lower bound the sign rank of such functions. This requires novel arguments that allow us to conclude that polynomials of low Fourier weight cannot approximate certain functions, even if they are allowed unrestricted degree.

This is based on joint work with Arkadev Chattopadhyay (TIFR, Mumbai).